//
// Created by PC on 2023/8/31.
// 二进制数相加
// https://leetcode.cn/problems/add-binary/submissions/
// 通过 用位运算实现 时间8ms和内存7.72MB都不理想
//


#include <iostream>
#include <string>

using namespace std;

string addBinary(string a, string b)
{
    // 让a变成长的串
    if (a.size() < b.size())
        swap(a, b);
    int lenB = b.size();
    // 让两个串的长度相等
    for (int i = 0; i < a.size() - lenB; ++i)
        b = "0" + b;
    // 按位异或^ 获取的是无进位相加的结果
    // 按位与&获取的是进位信息 再将进位信息向左移一位
    string aa, bb;
    for (int j = 0; j < a.size(); ++j)
    {
        int inta = (a[j] - '0');
        int intb = (b[j] - '0');
//        printf("%d ",inta^intb) ;
        aa += to_string(inta ^ intb);
        bb += to_string((inta & intb));
    }
    // 右边(低位)加0, 进位结果左移一位
    bb += '0';
    // 左边(高位)加0, 为了和bb对齐
    aa = '0'+aa;
//    cout<<"aa   "<<aa<<endl;
//    cout<<"bb   "<<bb<<endl;
    // 将无进位相加的结果aa  加上 进位的结果bb 存入ans
    int ans[aa.size()];
//    cout<<bb[0]-'0'<<endl;

    // aa,bb逐位相加
    for (int k = 0; k < aa.size(); ++k)
    {
        ans[k] = aa[k] - '0' + bb[k] - '0';
//        cout<<ans[k];
    }
    for (int l = b.size(); l >= 0; --l)
    {
        if (ans[l] == 2)
        {
            ans[l] = 0;
            ans[l - 1]++;
        } else if (ans[l] == 3)
        {
            ans[l] = 1;
            ans[l - 1]++;
        }
    }
    string ans_str;
    bool zero=true;
    for (int l = 0; l < bb.size() ; ++l)
    {
//        cout << ans[l];
        if (ans[l]!=0)
        {
            zero=false;
        }
        if (zero){
            continue;
        }
        char c = ans[l]+'0';
        ans_str.push_back(c);
    }
    if(ans_str.empty())
        ans_str="0";
    return ans_str;
}

int main()
{
    string a = "1111001", b = "1001001";
    a="11",b="1";
    a="0",b="0";
//    cin>>a>>b;
    cout<<addBinary(a,b);
    return 0;
}